/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/top-k-frequent-words-map-reduce
   @Language: C++
   @Datetime: 19-04-16 11:51
   */

/**
 * Definition of Input:
 * template<class T>
 * class Input {
 * public:
 *     bool done(); 
 *         // Returns true if the iteration has elements or false.
 *     void next();
 *         // Move to the next element in the iteration
 *         // Runtime error if the iteration has no more elements
 *     T value();
 *        // Get the current element, Runtime error if
 *        // the iteration has no more elements
 * }
 * Definition of Document:
 * class Document {
 * public:
 *     int id; // document id
 *     string content; // document content
 * }
 */
class TopKFrequentWordsMapper: public Mapper {
public:
	void Map(Input<Document>* input) {
		// Write your code here
		// Please directly use func 'output' to output 
		// the results into output buffer.
		// void output(string &key, int value);
		for(string str; !input->done(); input->next())
			for(stringstream istr(input->value().content); istr>>str;)
				output(str,1);
	}
};


class TopKFrequentWordsReducer: public Reducer {
	struct comp{
		bool operator()(const pair<string,int> &a, const pair<string,int> &b)const{
			if(a.second==b.second) return greater<string>()(a.first,b.first);
			return a.second<b.second;
		}
	};
	int k;
	set<pair<string,int>, comp> kset;
public:
	void setUp(int k) {
		// initialize your data structure here
		this->k=k;
	}

	void Reduce(string &key, Input<int>* input) {
		// Write your code here
		int count=0;
		for(; !input->done(); input->next())
			count+=input->value();
		kset.insert(make_pair(key,count));
		if(kset.size()>k) kset.erase(kset.begin());
	}

	void cleanUp() {
		// Please directly use func 'output' to output 
		// the top k pairs <word, times> into output buffer.
		// void output(string &key, int &value);
		for(auto it=kset.rbegin(); it!=kset.rend(); ++it){
			auto p=*it;
			output(p.first,p.second);
		}
	}
};
